#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define BUFFER_SIZE 10

static int swapNum(int *val1, int *val2)
{
    int tmpVal = *val1;
    *val1 = *val2;
    *val2 = tmpVal;
    return 0;
}


/* 快速排序:最快的排序
   基准值：一般设为第一个值
   (升序)我们要保证在   1.基准值的右边都要比基准值大
                      2.基准值的左边都要比基准值小
   用递归法（尽量不用，用不好会崩溃）
   非递归法
 */

/* 在指定范围内排序 */
static int innerQuickSort(int *nums, int begin, int end)
{
    if (begin >= end)
    {
        return 0;
    }

    /* 记录基准值 */
    int pivot = nums[begin];

    /* 很重要：备份begin & end */
    int tmpBegin = begin;
    int tmpEnd = end;
    while (begin < end)
    {
        while (begin < end)
        {
            /* 从右向左 */
            if (nums[end] >= pivot)
            {
                end--;
            }
            else
            {
                nums[begin++] = nums[end];
                break;
            }
        }
        while (begin < end)
        {
            /* 从左向右 */
            if (nums[begin] > pivot)
            {
                nums[end--] = nums[begin];
                break;
            }
            else
            {
                begin++;
            }
        }



    }
    /* 退出这个条件 begin == end */
    nums[begin] = pivot;
    /* 递归 */
    /* 第一轮之后注意更新范围，所以前面要备份 */
    innerQuickSort(nums, tmpBegin, begin - 1);
    innerQuickSort(nums, begin + 1, tmpEnd);

}
int quickSort(int *nums, int numSize)
{
    if (nums == NULL)
    {
        return 0;
    }    


    return innerQuickSort(nums, 0, numSize - 1);
}

int printNums(int *nums, int numSize)
{
    for (int idx = 0; idx < numSize; idx++)
    {
        printf("%d\t", nums[idx]);
    }
    printf("\n");
}

int main()
{
    int nums[BUFFER_SIZE] = {7, 21, 12, 5, 32, 45, 17, 87, 22, 9}; 

    quickSort(nums, BUFFER_SIZE);
    printNums(nums, BUFFER_SIZE);


    return 0;
}